#include "union.h"
Union::Union( )
{
}
Union::~Union()
{
   for( unsigned i = 0 ; i < (unsigned)_eqClass.size() ; ++i )
      if( data[i] == i ) delete _eqClass[i];
}
//--- set the varaible of content to be b 
void Union::set( const vec<unsigned> & a , unsigned b )
{
   unsigned * k=a.data;
   unsigned s = a.size();

   for(unsigned i = 0 ; i <s ; ++ i )
      data[ k[i] ] = b ;
}
//--- create a new group 
vec<unsigned> * Union::create( unsigned a , unsigned b)
{
   vec<unsigned>  * n = new vec<unsigned>(2);
   n->data[0] = a;
   n->data[1] = b;
   return n;
}
//--- union the group of a and group of b to be equivalent to "b"
void Union::conjunct( unsigned a, unsigned b)
{
   assert( a!=0);

   if( b != data[b] ) set( *(_eqClass[b]) , b );
   if( data[a] == data[b] )return;
   vec<unsigned> * va = _eqClass[a];
   vec<unsigned> * vb = _eqClass[b];

   if( va != NULL )
   {
      if( vb != NULL )
      {
         if( va->sz < vb->sz )
         {
            for(unsigned i = 0 ; i < va->size() ; ++ i )
            {
               unsigned n = va->data[i];
               data[ n ] = b,
               _eqClass[ n ] = vb,
               vb->push( n );
            }
            delete va;
         }else
         {
            set( *va,b);
            for(unsigned i = 0 ; i < vb->sz ; ++ i )
            {
               _eqClass[ vb->data[i] ] = va ;
               va->push( vb->data[i] );
            }
            delete vb;
         }
      }else
      {
         set( *va , b );
         va->push(b);
         _eqClass[b] = va;
      }
   }else
   {
      data[a] = b;
      if( vb != NULL )
      {
         vb->push(a);
         _eqClass[a] = vb;
      }else
      {         
         _eqClass[a] = _eqClass[b] = create( a , b );
      }
   }
}
void Union::validation( unsigned nsize )
{
   unsigned i = sz;
   resize( nsize ), _eqClass.resize( nsize , NULL );
   for( ; i < nsize ; ++ i ) data[i]=i;
}

